// https://www.lintcode.com/problem/di-string-match/

public class Solution {
    public int[] diStringMatch(String S) {
        /*
        测试几例子可以发现：I序列从0开始递增，D序列从len(S)开始递减。
        IDID
        - I 0
        - D 4
        - I 1
        - D 3
        - 2
        */
        int[] ret = new int[S.length() + 1];
        int start = 0, end = S.length();
        for (int i = 0; i < S.length(); ++i) {
            if (S.charAt(i) == 'I') {
                ret[i] = start;
                ++start;
            } else {
                ret[i] = end;
                --end;
            }
        }
        if (S.charAt(S.length() - 1) == 'I') {
            ret[S.length()] = start;
        } else {
            ret[S.length()] = end;
        }
        return ret;
    }
}